Algorithms in a Nutshell 2E by George T. Heineman Gary Pollice & Stanley Selkow

Author:George T. Heineman, Gary Pollice & Stanley Selkow
Language: eng
Format: epub
Tags: COMPUTERS / Programming / Algorithms
ISBN: 9781491912959
Publisher: O’Reilly Media
Published: 2015-07-28T04:00:00+00:00

Solution

The AlphaBeta implementation in Example 7-4 augments NegMax by terminating early the evaluation of game states once it becomes clear that either the player can’t guarantee a better position (an α-prune) or the opponent can’t force a worse position (a β-prune).

Example 7-4. AlphaBeta implementation

public class AlphaBetaEvaluation implements IEvaluation { IGameState state; /** State to be modified during search. */ int ply; /** Ply depth. How far to continue search. */ public AlphaBetaEvaluation (int ply) { this.ply = ply; } public IGameMove bestMove (IGameState s, IPlayer player, IPlayer opponent) { state = s.copy(); MoveEvaluation move = alphabeta(ply, player, opponent, MoveEvaluation.minimum(), MoveEvaluation.maximum()); return move.move; } MoveEvaluation alphabeta (int ply, IPlayer player, IPlayer opponent, int alpha, int beta) { // If no moves, return board evaluation from player's perspective. Iterator<IGameMove> it = player.validMoves(state).iterator(); if (ply == 0 || !it.hasNext()) { return new MoveEvaluation (player.eval(state)); } // Select "maximum of negative value of children" that improves alpha MoveEvaluation best = new MoveEvaluation (alpha); while (it.hasNext()) { IGameMove move = it.next(); move.execute(state); MoveEvaluation me = alphabeta (ply-1, opponent, player, -beta, -alpha); move.undo(state); // If improved upon alpha, keep track of this move. if (-me.score > alpha) { alpha = -me.score; best = new MoveEvaluation (move, alpha); } if (alpha >= beta) { return best; } // search no longer productive. } return best; } }

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.